package insertion_sort

import "fmt"

func Sort(data []int) (x []int) {
	for i := 1; i < len(data); i++ {
		a := data[i]
		j := i - 1
		for ; data[j] > a && j >= 0; j-- {
			data[j+1] = data[j]
		}
		data[j+1] = a
	}
	return data
}

func SortV2(data []int, insert func(int, []int)) []int {
	for i := 1; i < len(data); i++ {
		insert(i, data)
		fmt.Println(data)
	}
	return data
}

func Insert(n int, data []int) {
	i := n - 1
	x := data[n]
	for ; data[i] > x && i >= 0; i-- {
		data[i+1] = data[i]
	}
	data[i+1] = x
}

func BsInsert(n int, data []int) {
	x := data[n]
	i := BinarySearchV2(0, n-1, data[n], data)
	fmt.Println(i)
	j := n - 1
	for ; j >= i; j-- {
		data[j+1] = data[j]
	}
	data[j+1] = x

}

func BinarySearch(left, right, x int, data []int) int {
	mid := (left + right) / 2
	if left > right {
		return left
	}
	if x == data[mid] {
		return mid
	}

	if x > data[mid] {
		return BinarySearch(mid+1, right, x, data)
	}
	if x < data[mid] {
		return BinarySearch(left, mid-1, x, data)
	}
	return -1
}
func BinarySearchV2(left, right, x int, data []int) int {
	// right = right + 1
	for left <= right {
		mid := (left + right) / 2
		if data[mid] < x {
			left = mid + 1
		} else if data[mid] > x {
			right = mid - 1
		} else {
			return mid
		}
	}
	return left
}

func Swap(i, j int, data []int) {
	tmp := data[i]
	data[i] = data[j]
	data[j] = tmp
}
